While solving system of equations with the matrix A3 the situation is similar to the 2-dimensional case.
If coefficients σ = (σj)j=0,…,n in the matrix A3 are all the same, then it is possible to apply fast Fourier transform or cyclic reduction.
In this case we have the complexity of the problem is О(N log(N)), i.e. O(n3 log(n)).
However, if not all (σj)j=0,…,n are the same, then situation becomes more interesting:
The method of conjugate gradients provides the solution for O(n4.5) operation.
On the other hand, our method provides much smaller complexity of the solution - it has the same order of complexity as in 2D case - O(N) (where in 3D case N = n3).
This fact looks remarkable and gives significant improvement of performance. But even more remarkable is the fact that such a performance we achieve without any parallelization - when we work on a one-core processor...
If the hardware allows as much parallelization as we need (such a hardware might provide quantum computers), then complexity of the problem (with the method implemented in Marleen Solver) becomes O(1) !!!
However, we don't need to wait for implementation of quantum computers. Even nowadays GPU and cloud clusters provide remarkable opportunities for parallelization. The most powerful GPU already have thousands of cores.
It means that our Marleen Solver, launched on such a GPU, will work thousands times faster than in a single-thread mode. As for standard solvers, they are usually not well-suited for parallelization.